package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;

/**
 * MaxDepth 二叉树的最大深度
 * <p>
 * Description:
 * Given a binary tree, find its maximum depth.
 * The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
 * <p>
 * Input:
 * ----1
 * ---/ \
 * --2   3
 * -----/ \
 * ----4   5
 * Output:
 * 3
 * <p>
 * Created by heqianqian on 2017/9/13.
 */
public class MaxDepth {

    public static void main(String[] args) {
        /*data preparation*/
        TreeNode root = new TreeNode(1);
        TreeNode rChild = new TreeNode(3);
        rChild.left = new TreeNode(4);
        rChild.right = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = rChild;

        MaxDepth md = new MaxDepth();
        System.out.println(md.maxDepth(root));
    }

    /**
     * @param root: The root of binary tree.
     */
    public int maxDepth(TreeNode root) {
        // write your code here
        return depth(root);
    }

    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }
}
